1. Field of the Invention
This invention relates to a method and apparatus for decoding convolutionally encoded signals. Such signals are commonly used in communications and recording systems that employ error correction to combat signal corruption.
2. Description of the Related Art
The designers of mobile electronic devices such as cellular phones strive to reduce the power consumption of such devices. Lower power consumption leads to longer battery lives and thus greater convenience, greater reliability and reduced expenses for users of such devices. Therefore, manufacturers seek to differentiate themselves from competitors on the basis of reduced power consumption.
A major determinant of power consumption in cell phones (xe2x80x9cmobile stationsxe2x80x9d) is the amount of time the cell phone is actively receiving signals versus the amount of time the cell phone is in xe2x80x9cstandby mode,xe2x80x9d in which the mobile""s receiver is shut down. It is desirable to increase the amount of time the cell phone is in standby mode.
To reduce power consumption, certain types of cellular phone systems have a xe2x80x9cslottedxe2x80x9d mode, in which the mobile station xe2x80x9cknowsxe2x80x9d that any messages addressed to it will only be sent during specific frames. (A frame is a group of input symbols that are interleaved). These active frames are herein called the slot, and a slotted mode is one where this information to a specific mobile is transmitted only in that mobile""s assigned slot. Thus, the mobile can shut off its receiver for all other frames (xe2x80x9cstandby modexe2x80x9d). This is a crucial part of power management; therefore, it is highly desirable to increase the time the mobile is in standby mode.
Increasing the time the mobile is in standby mode depends upon, among other things, how much information the mobile must receive, and therefore the amount of time the receiver is on, to correctly process a given piece of data. In turn, the amount of information a mobile must receive to process data is critically dependent upon the coding/decoding scheme employed by the transmitter/receiver system; the mobile""s power consumption increases as the amount of information needed by the mobile to decode a given piece of data increases.
Coding/decoding schemes are employed in mobile communications systems to allow a mobile to detect and/or correct errors. (Additional layers of encoding/decoding may be applied for other reasons, such as security). These schemes function by adding some redundancy to information that is to be transmitted.
The redundancy, however, has a cost, in that the mobile must have more information to determine any particular symbol. Therefore, given a particular coding scheme, it is highly desirable to design a mobile that can estimate the desired symbol sequence based upon as little received information as possible, without significantly sacrificing the accuracy of such estimates.
One increasingly popular redundant coding scheme is convolutional coding, in which the coding of a sequence of precoding bits is passed through a shift register, which, at a particular point in time, outputs a certain number of encoded bits based upon the value of that portion of the sequence that is then in the register.
It would be desirable to improve upon conventional maximum likelihood sequence estimation (xe2x80x9cMLSExe2x80x9d) decoders such as Viterbi decoders, which are commonly used to decode convolutionally encoded data. If sk is a vector that represents a possible transmitted sequence of symbols and r is a vector that represents the actual signals received by a mobile, a Viterbi decoder effectively tests all of the possible values of sk and selects the sk that maximizes the summation xcexa3nc[n]r[n]sk[n]=skTCr, where c[n] defines the channel gain for a transmitted symbol for sample n (and thus C is a diagonal matrix with these values). (The sk that maximizes the cross correlation is the sk that minimizes the xe2x80x9cdistancexe2x80x9d between r and sk.) More generally, MLSE""s selects the sk that maximizes a function of the probability of sk given r. For more details regarding Viterbi decoders, see, for example, xe2x80x9cDigital Communicationsxe2x80x9d, John G. Proakis (3d edition 1995).
The best sk may be represented as a path through nodes in a diagram (known as a trellis), where lines (xe2x80x9ctransitionsxe2x80x9d) between nodes in adjacent time steps represent whether an input bit (preceding bit) was a 0 or a 1 (for binary coding). The nodes (xe2x80x9cstatesxe2x80x9d) in vertical columns represent the values of prior input symbols. A xe2x80x9cpathxe2x80x9d through the trellis therefore represents a particular sequence of input symbols. FIG. 1 shows an example of a trellis with only two paths 10 and 12 shown. The time steps indicate a decoder trellis beginning at time t=0 to time t=4. At each time step, the decision units of the decoder contain the value of the cross correlation of the most likely path to the state of interest. Thus, the decoder trellis contains multiple paths from an initial state to a given state several time steps later.
The path that has the highest cross correlation corresponds to the most likely sequence. The most likely path to a particular state within a given time step is found by starting at that particular state at that given time step and tracing backward (a xe2x80x9ctracebackxe2x80x9d) along the chosen transitions. Precoding bits that correspond to the transitions along the path are the decoded data. A preceding bit equal to 0 is shown is a solid line; a preceding bit equal to 1 is shown as a dotted line. Thus, path 10 shown in FIG. 1 corresponds to a precoding bit sequence equal to 0100 while path 12 corresponds to a precoding bit sequence equal to 1110.
Given a particular sequence received by a decoder, a metric is generated for possible test sequences, where each test sequence corresponds to a path through a trellis. For a path ending at a particular state at a particular time (xe2x80x9ccurrent nodexe2x80x9d), the corresponding metric is generated by adding (a) the metric for that portion of the path ending at a particular state at the previous time period (xe2x80x9cprior nodexe2x80x9d), to (b) the metric for the transition from the prior node to the current node. (According to the Viterbi algorithm, metrics are generated for all possible paths ending in a current node and the path with the highest metric is the survivor path; the other paths are discarded.) For example, assume that the portion of the path 10 that ends at node 22 in FIG. 1, which corresponds to encoder state B at time t=3, has a metric of 4. If the metric for the transition from node 22 to a node 20 is 2, the metric for the entire path 10 is 6 (=4+2). The path at any given time with the highest metric is the most likely path and is therefore the path that is xe2x80x9ctraced back.xe2x80x9d
To achieve good noise performance from the decoding process, the traceback length must generally be several times the constraint length (the number of input bits upon which an output depends; this is one plus the length of a shift register that may be used to perform the encoding) of the code. For example, assume a code with a constraint length of 9 that outputs 2 coded bits for each input bit. If a decoder for such a coding scheme has been running from t=xe2x88x92∞ to t=0 and a traceback is then performed, the last 64 bits might not achieve adequate error performance, while those prior to those 64 will have been accurately decoded. This discrepancy occurs because for the most recent bits there is still subsequent information (that can help to decode those most recent bits) in the not yet arrived signal.
On the other hand, if the decoder must wait for subsequent information, the power consumption of the mobile may be increased. Similarly, power consumption may be increased if, at the beginning of an encoded data stream that a decoder must decode, the decoder must know information transmitted prior to such data. For example, assume there are three frames, and the actual information) intended for the user of the mobile is only in the second frame. Optimally, the mobile should receive only that second frame because reception of the other two frames dissipates power. However, if the decoder must know information from the past frame to decode the start of the present frame, or if the decoder must know information from a subsequent frame to decode the end of the current frame (i.e. tracebacks extend between frames), the mobile""s decoder will need to receive information from the first and third frames
FIG. 1 illustrates the problems described in the previous paragraph. Assume that the transition from a node at time t=0 to a node at time t=1 is caused by the first precoding bit of a frame which corresponds to the first transmitted bits of that frame. At time t=0, the decoder must know the metric for the paths ending at different states at time t=0; this requires knowledge of transmitted bits from the prior frame. Similarly, if time t=4 is assumed to be the end of a frame, in order to perform a traceback from a subsequent time to time t=4, by definition the decoder must have information after time t=4.
The problem is compounded by the interleaving of frames: an entire frame must be received and deinterleaved before it is available for decoding. Therefore, if tracebacks extend between frames, for systems with deinterleaving, the first and third frames must be received in their entirety to properly decode the second frame; the receiver consumes power when it receives the first and third frames.
As an example of the above mentioned problem, FIG. 2 shows a timeline of mobile station activity for one type of slotted mode system. As shown, a mobile unit is allocated a particular slot comprising four frames. Outside of the slot, no end user information for the mobile is transmitted. To conserve power, it is desirable to require the mobile to receive as little as possible of the signal outside of the slot. However, as previously described, due to the nature of interleaving and convolutional codes, some types of conventional mobiles often must receive the frame before frame 1 to decode frame 1 and also must receive the frame after frame 4 to decode frame 4. This is highly undesirable from a power consumption standpoint.
xe2x80x9cTailedxe2x80x9d convolutional codes are a conventional method for eliminating the requirement that prior and subsequent frames must be received before a present frame may be decoded. In a tailed convolutional code, a xe2x80x9ctailxe2x80x9d is added to the input bit stream (i.e. prior to encoding) at the end of every frame or some subset of frames. The tail would commonly be Kxe2x88x921 zeros, where K is the constraint length of the code and thus Kxe2x88x921 is the number of registers in an encoder""s shift register. Thus, for a code with a constraint length of 9, the state at the end and beginning of a frame is known to be [00000000]. Since the state at the beginning of the current frame is known, there is no need to receive the prior frame.
In addition, since the state at the end of the frame is known, there is no need to receive the subsequent frame (and thus no need to perform a traceback from the subsequent frame into the current frame to decode the portions, especially end portions, of the current frame). In other words, an entire current frame can be optimally decoded as soon as the last symbol of the frame is received. For example, if the decoder knows that the encoder was in the state A (node 14) at time t=0 in FIG. 1, then there is no need to perform a traceback to nodes at times t less than 0.
Instead of a full tail as discussed above, some systems add a partial tail where the number of zeros appended to a frame is less than Kxe2x88x921. In this case the start and end states for a frame are not known, but a large subset of the states can be discarded as impossible. For example, if 4 tail bits are added using the example code discussed above, then only 16 out of the full set of 256 states are possible. These states may be denoted [0000xxxx] where the digits to the right are the earlier precoding bits inserted into the shift register. If a prior frame is not received, tracebacks can end only in one of these possible states. In this case, decoding will be faster because the prior frame need not be received but performance will be sacrificed.
Although tailed convolutional codes enable a receiver to decode a frame without having to receive prior and subsequent frames, some popular systems do not employ tailed convolutional codes in all circumstances. For example, the IS-95 standard provides for tailing during xe2x80x9ctrafficxe2x80x9d mode but not during xe2x80x9cpagingxe2x80x9d mode. Nonetheless, to avoid having to receive subsequent and prior frames, some receivers assume that a fixed tail has been applied, which, if that is not the case, results in a relatively higher error rate.
Therefore, it would be desirable for a receiver to have the capability to decode a present frame with an acceptable error rate, without having to receive prior or subsequent frames, for a non-tailed or only partially tailed convolutional code.
These and other needs are met by the present invention, which provides a method and apparatus for decoding transmitted data that has been generated by encoding precoding bits with a convolutional encoder that generates convolutional codes based on an input sequence of precoding bits, where the encoder has a constraint length K and a rate k/n.
In the preferred embodiment, the decoding of received data is performed by receiving a sequence of data r which resulted from the encoding and transmission of a preceding sequence through a channel and the reception of that sequence. The preceding sequence consists of two subsequences t and b; the value of t corresponds to an encoder state at a particular time. For example, t may be the last Kxe2x88x921 precoding bits of a prior frame while b may be all of the preceding bits of a present frame. The a priori probability Pr(ti) that the subsequence t has a particular value ti is generated. In the preferred embodiment, the metric function that is applied to a test sequence that includes ti is then biased by adding (("sgr"2/xcex12). In(Pr(ti)), where xcex12 is the signal average energy for each symbol of the transmitted data, "sgr"2 is the variance of the noise added to a symbol by a channel through which the symbol is transmitted. The resulting metric is then used by an MLSE decoder such as a Viterbi decoder to decode the received data.